package maxheap;

import queue.PriorityQueue;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

public class Solution {
    /**
     * leetcode 347 前K个高频元素
     *
     * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
     *
     * 示例 1:
     *
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     * 示例 2:
     *
     * 输入: nums = [1], k = 1
     * 输出: [1]
     * 说明：
     *
     * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
     * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
     */
    public List<Integer> topKFrequent(int[] nums, int k) {

        // 统计词频,放入TreeMap中
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        // 存放k个优先级高的队列, 基于最大堆
        PriorityQueue<Freq> pq = new PriorityQueue<>();

        // 对每个map中的元素,先添加k个到队列中,
        // 剩下的逐个与该优先队列频次最低(优先级最高)的队首元素进行比较,
        // 如果频次大(优先级低)的则入队且队首元素出队
        for (int key: map.keySet()) {
            if(pq.getSize() < k){
                pq.enqueue(new Freq(key, map.get(key)));
            } else if(map.get(key) > pq.getFront().freq) {
                pq.dequeue();
                pq.enqueue(new Freq(key, map.get(key)));
            }
        }
        // 返回该优先队列
        LinkedList<Integer> res = new LinkedList<>();
        while(!pq.isEmpty()){
            res.add(pq.dequeue().e);
        }
        return res;
    }

    /**
     * 频率高的优先级低(即 小), 频率低的优先级高(即 大)
     */
    private class Freq implements Comparable<Freq> {
        int e, freq;

        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }
        @Override
        public int compareTo(Freq another) {
            if(this.freq < another.freq) {
                return 1;
            } else if(this.freq > another.freq) {
                return -1;
            } else {
                return 0;
            }
        }
    }

    /*
    如果使用的是java自带的PriorityQueue,可在构造函数传入该比较器
    private class FreqComparator implements Comparator<Freq> {

        @Override
        public int compare(Freq o1, Freq o2) {
            return o1.freq - o2.freq;
        }
    }*/
}

class Solution2{
    /**
     * leetcode 347 前K个高频元素
     *
     * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
     *
     * 示例 1:
     *
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     * 示例 2:
     *
     * 输入: nums = [1], k = 1
     * 输出: [1]
     * 说明：
     *
     * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
     * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
     */
    public List<Integer> topKFrequent(int[] nums, int k) {

        // 统计词频,放入TreeMap中 元素:频率
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }

        // 存放k个优先级高的队列, 基于最大堆
        java.util.PriorityQueue<Integer> pq = new java.util.PriorityQueue<>(/*new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        }*/
                (a, b) -> map.get(a) - map.get(b)
        );

        // 对每个map中的元素,先添加k个到队列中,
        // 剩下的逐个与该优先队列频次最低(优先级最高)的队首元素进行比较,
        // 如果频次大(优先级低)的则入队且队首元素出队
        for (int key: map.keySet()) {
            if(pq.size() < k){
                pq.add(key);
            } else if(map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }
        // 返回该优先队列
        LinkedList<Integer> res = new LinkedList<>();
        while(!pq.isEmpty()){
            res.add(pq.remove());
        }
        return res;
    }

}
